1. Field of the Invention
The present invention relates to the task of managing packet flows in a computer network. More specifically, the present invention relates to a method and an apparatus for resolving conflicts between network service rule sets for network data traffic in a system where rule patterns with longer prefixes match before rule patterns with shorter prefixes.
2. Related Art
Dramatic advances in networking technology presently make it possible to transfer data at bandwidths exceeding 2.5 gigabits per second across a single high-speed optical pipe. These high-speed pipes can be used to connect data centers to wide area networks and the Internet. In order to effectively use the bandwidth available through these high-speed pipes, edge devices within the data centers must be able to manage the packet flows received through these pipes. For example, an edge device can perform a number of operations related to managing network flows, such as performing firewall functions, service level agreement (SLA) monitoring, transport matching and load balancing. Performing these operations can be an extremely challenging task because the policies specifying how packet flows need to be modified as they are received at high transfer rates need to be managed. Furthermore, the devices used to perform the enforcement need to be constructed such that they scale to high data rates in a reliable fashion.
These operations are typically applied to packet flows in a pipelined fashion. For example, referring to FIG. 1, a packet flow received through high-speed pipe 102 feeds through a pipeline that includes a number of separate modules, including a firewall module 104, an SLA monitoring module 105, a transport matching module 106 and a load-balancing module 107. The output of this pipeline feeds through a switch 108, which switches packets to various servers 110-112 within the data center. This pipelined architecture allows the modules to operate sequentially on the packet flow. However, passing the packet flow through multiple pipeline stages increases latency, which can adversely affect performance for many applications.
Note that each of these pipeline modules can conceptually be divided into three components: (1) a classifier and dispatch component; (2) a module-specific component that directly operates on the packets in the packet flow; and (3) a management and administration component that generates rules for the classifier and dispatch component. (Note that the classifier and dispatch component and the module-specific component are collectively referred to as the “data plane,” whereas the management and administration component is referred to as the “control plane”). In this way, the high-speed classification and dispatch operations performed by the data plane can be separated from the management and administration functions performed by the control plane. FIG. 2 illustrates how the modules in FIG. 1 can be separated into separate control plane and data plane modules.
A standardized interface is being developed to facilitate this separation. In particular, see the paper entitled “Open Standards for the Control and Forwarding Planes in Network Elements,” by Lily L. Yang, Ram Gopal and Susan Hares, which describes an early attempt to standardize the interface between the control and forwarding planes. A standardized interface allows system vendors to use components from different suppliers to perform these control and forwarding functions.
In order to provide additional performance, a number of pipelines can operate in parallel. For example, referring to FIG. 3, the packet flow from high-speed pipe 102 is routed into three parallel pipelines by fan out module 300. The outputs of these pipelines feed into switch 108, which switches packets from the pipelines to various servers 110-112 within the data center.
Providing parallel pipelines can improve performance if the packet stream can be divided into separate flows for the different pipelines. However, it does not help if the packet stream contains only a single flow. Moreover, this technique does not reduce the number of pipeline stages, and consequently does little to reduce latency.
In order to solve the above-described problems, it is desirable to collapse the various operations related to managing network flows into a single flow classification and dispatch step. This reduces the latency involved in applying the operations to the packet flow in pipelined fashion as is illustrated in FIGS. 1-3. However, in order to collapse the operations in this way, it is necessary to resolve conflicts between rules for the various network services, such as load balancing and firewall services. (These rules will be subsequently referred to as “network service rules.”).
The conflict resolution process is complicated by the fact that existing packet-processing hardware is designed so that rule patterns with longer prefixes match before rule patterns with shorter prefixes. This generally makes sense because a rule with a longer prefix applies to a more-specific set of packets, and is hence likely to take precedence over a more general rule that applies to a larger set of packets. However, in some cases it is desirable for a rule with a shorter prefix to have a higher priority than a rule with a longer prefix. For example, it is typically desirable for rule that originates from a firewall service, which filters out potentially malicious packets, to have a higher priority than a rule that originates from a load-balancing service, even if the rule for the load-balancing service has a longer prefix.
Hence, what is needed is a method and an apparatus that resolves conflicts between network service rules for network data traffic in a system where rule patterns with longer prefixes match before rule patterns with shorter prefixes.